#include <iostream>
#include <vector>
#include <string>
using namespace std;

template<typename T>
class Stack {
private:
    vector<T> items;
    
public:
    // 入栈
    void push(T item) {
        items.push_back(item);
        cout << "入栈: " << item << endl;
    }
    
    // 出栈
    T pop() {
        if (isEmpty()) {
            throw runtime_error("栈为空");
        }
        T item = items.back();
        items.pop_back();
        cout << "出栈: " << item << endl;
        return item;
    }
    
    // 查看栈顶元素
    T peek() {
        if (isEmpty()) {
            throw runtime_error("栈为空");
        }
        return items.back();
    }
    
    // 判断栈是否为空
    bool isEmpty() {
        return items.empty();
    }
    
    // 获取栈的大小
    int size() {
        return items.size();
    }
    
    // 打印栈内容
    void print() {
        cout << "栈内容: ";
        for (int i = 0; i < items.size(); i++) {
            cout << items[i] << " ";
        }
        cout << endl;
    }
};

// 括号匹配函数
bool isValidParentheses(string s) {
    Stack<char> stack;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || 
                (c == '}' && top != '{') || 
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

int main() {
    cout << "=== 栈的基本操作测试 ===" << endl;
    
    Stack<int> stack;
    
    // 基本操作测试
    stack.push(1);
    stack.push(2);
    stack.push(3);
    
    stack.print();
    cout << "栈顶元素: " << stack.peek() << endl;
    cout << "栈大小: " << stack.size() << endl;
    
    stack.pop();
    stack.print();
    
    cout << "\n=== 括号匹配测试 ===" << endl;
    string test1 = "()[]{}";
    string test2 = "([)]";
    
    cout << test1 << " -> " << (isValidParentheses(test1) ? "有效" : "无效") << endl;
    cout << test2 << " -> " << (isValidParentheses(test2) ? "有效" : "无效") << endl;
    
    return 0;
}
